package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_054_SpiralMatrix {
    public static void main(String[] args) {

    }

    static class Solution {

        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            if (matrix.length == 0)
                return res;
            int rows = matrix.length;
            int cols = matrix[0].length;
            // 此种方法关键点--求圈数
            // 最小值除以2，向上取整
            // int layers = (Math.min(rows, cols) - 1) / 2 + 1;
            int layers = (int) Math.ceil((Math.min(rows, cols)) / 2.0);

            // 要打印的圈数
            for (int i = 0; i < layers; i++) {
                // 打印每圈
                // 左至右
                for (int k = i; k < cols - i; k++)
                    res.add(matrix[i][k]);

                // 右上至右下
                for (int j = i + 1; j < rows - i; j++)
                    res.add(matrix[j][cols - i - 1]);

                // 注意k,j开始的下标
                // 右至左
                // (rows - i - 1 != i)避免重复打印第i行
                for (int k = cols - i - 2; (k >= i) && (rows - i - 1 != i); k--)
                    res.add(matrix[rows - i - 1][k]);

                // 左下至左上
                // (cols - i - 1 != i)避免重复打印第i列
                for (int j = rows - i - 2; (j > i)
                        && (cols - i - 1 != i); j--)
                    res.add(matrix[j][i]);
            }
            return res;
        }


    }


    static class Solution_2 {

        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            if (matrix.length == 0) {
                return res;
            }
            int up = 0;
            int down = matrix.length - 1;
            int left = 0;
            int right = matrix[0].length - 1;
            // 取到‘=’是因为走过的已经移动指针
            while (up <= down && left <= right) {
                // Traverse Right(→)
                for (int j = left; j <= right; j++) {
                    res.add(matrix[up][j]);
                }
                up++;

                // Traverse Down(↓)
                for (int j = up; j <= down; j++) {
                    res.add(matrix[j][right]);
                }
                right--;

                if (up <= down) {
                    // Traverse Left(←)
                    for (int j = right; j >= left; j--) {
                        res.add(matrix[down][j]);
                    }
                }
                down--;

                if (left <= right) {
                    // Traver Up(↑)
                    for (int j = down; j >= up; j--) {
                        res.add(matrix[j][left]);
                    }
                }
                left++;
            }

            return res;
        }

    }

}
